package vip.zhenzicheng.algorithm.leetcode.binary_search;

/**
 * <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/">在排序数组中查找元素的第一个和最后一个位置 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-17 13:59
 */
public class FindFirstAndLastPositionOfElementInSortedArray_34 {

  public int[] searchRange(int[] nums, int target) {
    int[] result = new int[2];
    result[0] = findFirst(nums, target);
    if (result[0] == -1) return new int[]{-1, -1}; // 左边都没找到就不用再找右边了
    result[1] = findLast(result[0], nums, target);
    return result;
  }

  private int findFirst(int[] nums, int target) {
    int idx = -1;
    int start = 0;
    int end = nums.length - 1;

    while (start <= end) {
      int mid = (start + end) / 2;
      if (nums[mid] >= target) { // 等于也得继续往左找，直到是第一次出现
        end = mid - 1;
      } else {
        start = mid + 1;
      }

      if (nums[mid] == target) idx = mid; // 记录本次出现的位置
    }
    return idx;
  }

  private int findLast(int first, int[] nums, int target) {
    int idx = -1;
    int start = first;
    int end = nums.length - 1;
    while (start <= end) {
      int mid = (start + end) / 2;
      if (nums[mid] <= target) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }

      if (target == nums[mid]) idx = mid;
    }
    return idx;
  }
}
